class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode() {
	}

	TreeNode(int val) {
		this.val = val;
	}

	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

/**
 * 拆分中序非递归遍历
 */
public class BSTIterator {
	private TreeNode curNode;
	private Deque<TreeNode> stack;

	public BSTIterator(TreeNode root) {
		curNode = root;
		stack = new ArrayDeque<>();
	}

	public int next() {
		while (curNode != null) {
			stack.offerLast(curNode);
			curNode = curNode.left;
		}
		curNode = stack.pollLast();
		int val = curNode.val;
		curNode = curNode.right;
		return val;
	}

	public boolean hasNext() {
		return curNode != null || !stack.isEmpty();
	}
}
